package lc;

import java.util.HashMap;
import java.util.Map;

/**
 * 给定一个整数数组 A，返回其中元素之和可被 K 整除的（连续、非空）子数组的数目。
 */
public class Q974 {

    public int subarraysDivByK(int[] A, int K) {
        // 思路是
        Map<Integer, Integer> record = new HashMap<>();
        record.put(0, 1);
        int sum = 0;
        int times = 0;
        // 思路是两个前缀和之差如果是被k整除，那么第一个前缀和和第二个前缀和和k除余一样
        for (int i : A) {
            sum += i;
            int r = (sum % K + K) % K;
            record.putIfAbsent(r, 0);
            Integer t = record.get(r);
            times += t;
            record.put(r, t + 1);
        }
        return times;
    }

    public static void main(String[] args) {
        final Q974 q974 = new Q974();
        final int i = q974.subarraysDivByK(new int[]{
                4, 5, 0, -2, -3, 1
        }, 5);
        System.out.println(i);
    }
}
